package leetcode.daily;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : zx
 * @version V1.0
 */
public class a_20201218 {

    /**
     * 887. 鸡蛋掉落
     * 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。
     *
     * 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
     *
     * 你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
     *
     * 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
     *
     * 你的目标是确切地知道 F 的值是多少。
     *
     * 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
     *
     *
     *
     * 示例 1：
     *
     * 输入：K = 1, N = 2
     * 输出：2
     * 解释：
     * 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
     * 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
     * 如果它没碎，那么我们肯定知道 F = 2 。
     * 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
     * 示例 2：
     *
     * 输入：K = 2, N = 6
     * 输出：3
     * 示例 3：
     *
     * 输入：K = 3, N = 14
     * 输出：4
     *
     *
     * 提示：
     *
     * 1 <= K <= 100
     * 1 <= N <= 10000
     */
    private static int[][] dp = null; // 记忆K，N对应最少次数 简化计算
    public static int superEggDrop(int K, int N) {
        dp = new int[K+1][N+1];
        // 初始化最简状态
        for(int i = 0; i <= N; i++){
            dp[1][i] = i; // 如果只有一个蛋 则只能线性查找 次数为i
        }
        for(int i = 1; i <= K; i++){
            dp[i][1] = 1; // 如果只有一层 不管有几个蛋 都只需要一次
        }
        return recurse(K, N);
    }
    private static int recurse(int K, int N){
        if(K == 0 || N == 0) return 0; // 出现0 说明已经找到了 不需要次数
        if(dp[K][N] != 0) return dp[K][N]; // 已记忆直接返回
        // 选择从1-N层楼 哪层扔次数最少
        // ！ 注意 i recurse(K, N-i) 和 recurse(K-1, i-1)分别为单调递减和递增函数 因此可以使用二分法查找交点 两侧的值 这里查找左侧的临近点
        int l = 1, r = N;
        while(l+1 < r){
            int i = l + (r-l)/2;
            int t1 = recurse(K-1, i-1), t2 = recurse(K, N-i);
            if(t1 == t2) r = l = i;
            else if(t1 > t2) r = i;
            else if(t2 > t1) l = i;
        }

        int result = Math.min(
                Math.max(
                        recurse(K-1, l-1), // 碎了 则选择下方的
                        recurse(K, N-l) // 没碎则在上面找
                ),
                Math.max(
                        recurse(K-1, r-1), // 碎了 则选择下方的
                        recurse(K, N-r) // 没碎则在上面找
                )
        )+1;
        dp[K][N] = result;
        return dp[K][N];
    }

    /**
     * 146. LRU 缓存机制
     * 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
     * 实现 LRUCache 类：
     *
     * LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
     * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
     * void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
     *
     *
     * 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
     *
     *
     *
     * 示例：
     *
     * 输入
     * ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
     * [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
     * 输出
     * [null, null, null, 1, null, -1, null, -1, 3, 4]
     *
     * 解释
     * LRUCache lRUCache = new LRUCache(2);
     * lRUCache.put(1, 1); // 缓存是 {1=1}
     * lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
     * lRUCache.get(1);    // 返回 1
     * lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
     * lRUCache.get(2);    // 返回 -1 (未找到)
     * lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
     * lRUCache.get(1);    // 返回 -1 (未找到)
     * lRUCache.get(3);    // 返回 3
     * lRUCache.get(4);    // 返回 4
     *
     *
     * 提示：
     *
     * 1 <= capacity <= 3000
     * 0 <= key <= 3000
     * 0 <= value <= 104
     * 最多调用 3 * 104 次 get 和 put
     */
    static class LRUCache {

        Node Head;
        Node Tail;
        Map<Integer, Node> map;
        int capacity;
        int size = 0;

        private class Node{
            int key;
            int value;

            Node pre;
            Node next;

            void moveToHead(){
                if(pre == null || next == null){
                    // 新节点
                    if(Head.next == null && Tail.pre == null){
                        Tail.pre = this;
                        Head.next = this;
                        this.next = Tail;
                        this.pre = Head;
                    }else {
                        this.next = Head.next;
                        this.pre = Head;
                        Head.next.pre = this;
                        Head.next = this;
                    }
                }else if(pre == Head){
                    // 原来为头
                }else if(next == Tail){
                    Tail.pre = pre;
                    pre.next = next;
                    Head.next.pre = this;
                    this.next = Head.next;
                    this.pre = Head;
                    Head.next = this;
                }else {
                    this.pre.next = this.next;
                    this.next.pre = this.pre;
                    Head.next.pre = this;
                    this.next = Head.next;
                    this.pre = Head;
                    Head.next = this;
                }
            }

            void delete(){
                if(pre == null || next == null){
                    // 不需要操作
                }else if(pre == Head){
                    Head.next = next;
                    next.pre = Head;
                }else if(next == Tail){
                    Tail.pre = pre;
                    pre.next = Tail;
                }else{
                    pre.next = next;
                    next.pre = pre;
                }
            }

            public Node(int key, int value){
                this.key = key;
                this.value = value;
            }
        }

        public LRUCache(int capacity) {
            Head = new Node(0,0);
            Tail = new Node(0,0);
            map = new HashMap<>();
            this.capacity = capacity;
        }

        public int get(int key) {
            Node curr = map.get(key);
            if(curr == null) return -1;
            else{
                curr.moveToHead();
                return curr.value;
            }
        }

        public void put(int key, int value) {
            Node curr = map.get(key);
            if(curr != null){
                curr.value = value;
                curr.moveToHead();
            }else{
                curr = new Node(key, value);
                if(size >= capacity){
                    int old = Tail.pre.key;
                    map.remove(old);
                    Tail.pre.delete();
                    curr.moveToHead();
                }else{
                    size++;
                    curr.moveToHead();
                }
                map.put(key, curr);
            }
        }
    }

    public static void main(String[] args){
//        System.out.println(superEggDrop(6,5000));
        LRUCache l = new LRUCache(3);
        l.put(1,1);
        l.put(2,2);
        l.put(3,3);
        l.put(4,4);
        l.get(4);
        l.get(3);
        l.get(2);
        l.get(1);
        l.put(5,5);
        l.get(1);
        l.get(2);
        l.get(3);
        l.get(4);
        l.get(5);
    }
}
